Synchronization Hardware

• 許多系統提供硬體執行critical section(CS)程式碼的支持。
• lock：保護CS。
• atomic：不能被interrupt。
• 要達到lock的功能需要兩個基本指令：

1. test memory word and set value
2. swap contents of two memory words：將兩個memory words的內容做交換。

• 總體來說，把CS用locking鎖住，然後在uniprocessdr的時候，將interrupt給禁止掉，就不會發生任何preemption的情況。但這是一個非常不好的方法，沒有效率，所以需要用到atomic方法。
• 程式說明：
  do {
  acquire lock /用lock鎖住CS/
  critical section
  release lock /執行完工作，釋放CS/
  remainder section
  } while (TRUE)；

test_and_set Instruction

• 程式說明：
  boolean test_and_set (boolean *target)
  {
  boolean rv = *target；
  *target = TRUE；
  return rv；
  }
  ==>這一整段都是個「atomic」，因為不能被中斷。
  ==>將進入的參數設成TRUE，所以原本在裡面的參數會被return出去，就可以形成一個lock的動作。

Solution using test_and_set()

• 程式說明：
  ==>將一開始的初始值設成false，所以不能進入。
  do {
  while (test_and_set(&lock)；
  /* do nothing / /如果是false的話，便不做任何事/
  / critical section / /如果是true的話，便進入CS執行/
  lock = false； /執行完畢，從CS中出來/
  / remainder section */
  } while (true);

compare_and_swap Instruction

• 程式說明：
  int compare_and_swap(int * value, int expected, int new_value) {
  int temp = *value；

                    if (*value == expected)
                       *value = new_value；
                return temp；
                }
  

==>總共會有三個value，分別是「original value(原來值)」、「expected value(期待值)」、「new_value」。
==>return原來值出去，數值進入後判斷variable的value有無跟期待值一樣，如果一樣的話，就將new_value設成value，然後將原來的value return會來，將內容作swap的動作。

Mutex Lock - Spinlock

• OS的設計者會建立software tools去解決CS的問題。
• 而software tools包含mutex lock跟spinlock。
• 最簡單的方法是mutex lock。
• 會使用兩種方法來取得與釋放lock：

1. acquire()：取得lock
2. release()：釋放lock

• acquire()與release()必須是atomic，且透過硬體指令執行。
  * busy waiting：如果以上兩種方法沒有取到lock的話，將會處於一種「busy waiting」的狀態，一直在等待，直到可以進入CS並完成後，會release lock，所以此lock會被稱作為「Spinlock」，由busy waiting的方式進行。

Semaphore

• 是個Synchronization tool，提供更複雜、尖端的方法給process去同步活動。
• 大部分系統皆有支持。
• Semaphore S是一個整數變數(integer variable)。
• 可透過兩個方法去執行：

1. wait()
2. signal()
   ==>而這兩個方法在過去被稱作為P()與V()。
   ==>也是個不可被中斷的方法。

Semaphore Usage

• Binary semaphore：整數變數的範圍僅限於0~1之間。

1. 類似於mutex lock。

• 可以解決多樣化的synchronization problems。
• 有兩個行程P1與P2，以及operation的S1與S2，且要求S1必須在S2之前發生。
• 可以做到強迫順序的達成。

Semaphore Implementation

• 在實作時，必須保證在同一時間，不能在同一個semaphore內有兩個process執行wait()跟signal()。
• 當wait()和signal()被放置在CS中，會變成CS problem。

1. 現在多使用busy waiting方法處理，但並不是最有效率的方法。

• 應用程式會花費很多時間在CS，所以也不是個好方法。

Semaphore Implementation with no Busy waiting

• 每個semaphore會連接著一個waiting queue。
• 每個進入waiting queue的都會有兩個data items：

1. value(一種整數)
2. pointer to next record in the list

• 基本兩個operations：

1. block:把process放進waiting queue裡。
2. wakeup：把process從waiting queue中拿出來。

• 比busy waiting更有效率

Deadlock and Starvation

• Deadlock：兩個process在互相等待被對方占住的資源。
• Starvation：無限期的blocking；有一個行程可能永遠不會從semaphore wating queue中移出來。
• Priority Inversion：是一個排程問題，也就是低優先權的process佔住了高優先權process的資源，如果想要解決這個問題的話，就要透過priority-inheritance protocol解決。